package com.zwxu.list;

import java.util.LinkedList;
import java.util.List;

public class RemoveDuplicatesDemo {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		ListNode node1 = new ListNode(1);
		ListNode node2 = new ListNode(1);
		ListNode node3 = new ListNode(3);
		ListNode node4 = new ListNode(4);
		ListNode node5 = new ListNode(4);
		node1.next = node2;
		node2.next = node3;
		node3.next = node4;
		node4.next = node5;
		// ListNode temp = node1;
		ListNode temp = deleteDuplicates3(node1);
		while (temp != null) {
			System.out.print(temp.val + ">");
			temp = temp.next;

		}
	}

	/*
	 * 复杂度最低  借助两个指针 O(n)
	 */
	public static ListNode deleteDuplicates3(ListNode head) {
		if (head == null) {
			return null;
		}
		ListNode tail = head; // 指向新结点的尾部，开始时新链只有一个元素，就是链头
		ListNode point = head.next; // 指向另一个链的头部
		while (point != null) { // 另一个链还未到末尾
			if (tail.val != point.val) { // 如果与尾节点不相同，就将不相同的节点链接到tail的下一个位置
				tail.next = point;
				tail = tail.next; // 重新指向链尾
			}
			point = point.next;
		}
		tail.next = null; // 链尾指向空

		return head;
	}

	public static ListNode deleteDuplicates2(ListNode head) {
		if (head == null) {
			return null;
		}
		// 利用前后指针
		ListNode current = head;
		ListNode pre = head;
		// 1-1-3-3-1 第一趟 找重复1 第二趟找重复3
		while (current.next != null) {
			current = current.next;
			int value = pre.val;
			while (current.val == value) {
				if (current.next == null) {
					pre.next = null;
					break;
				}
				pre.next = current.next;
				current = current.next;
				if (current == null) {
					break;
				}
			}
			pre = pre.next;
		}
		return head;
	}

	/*
	 * 复杂度过高
	 */
	public static ListNode deleteDuplicates(ListNode head) {
		if (head == null) {
			return null;
		}
		List<Integer> list = new LinkedList<Integer>();
		ListNode cur = head;
		while (cur != null) {
			if (!list.contains(cur.val)) {
				list.add(cur.val);
			}
			cur = cur.next;
		}
		ListNode newHead = new ListNode(list.get(0));
		ListNode node = newHead;
		for (int i = 1; i < list.size(); i++) {
			node.next = new ListNode(list.get(i));
			node = node.next;
		}
		return newHead;
		// write your code here
	}

}
